package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了90.55%的用户
内存消耗：3.2 MB, 在所有 Go 提交中击败了56.88%的用户
 */
func search(nums []int, target int) bool {

	R := len(nums) - 1
	for R >= 0 && nums[R] == nums[0] { R-- }
	if R < 0 { return nums[0] == target }

	l, r := 0, R
	for l < r {
		mid := (l + r + 1) >> 1
		if nums[mid] >= nums[0] {
			l = mid
		} else {
			r = mid - 1
		}
	}

	if target >= nums[0] {
		l = 0
	} else {
		l++
		r = R
	}

	for l < r {
		mid := (l + r) >> 1
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}

	return nums[r] == target
}

func main() {

	nums := []int{2, 5, 6, 0, 0, 1, 2}
	fmt.Println(search(nums, 0))  // true
}
